import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution1377 {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(1);
        int[] visit=new int[n+1];
        int[] pre=new int[n+1];
        int[] cha=new int[n+1];
        Arrays.fill(visit,Integer.MAX_VALUE);
        visit[1]=0;
        pre[1]=-1;
        while (!queue.isEmpty()){
            int p=queue.poll();
            for (int[] edge : edges) {
                if (edge[0]==p || edge[1]==p){
                    int v=edge[0]+edge[1]-p;
                    if (visit[v]>visit[p]+1){
                        visit[v]=visit[p]+1;
                        pre[v]=p;
                        cha[p]++;
                        queue.offer(v);
                    }
                }
            }
        }
        double ans=1;
        if (visit[target]>t){
            return 0;
        }
        boolean flag=true;
        for (int i=1;i<=n;i++){
            if (pre[i] == target) {
                flag = false;
                break;
            }
        }
        if (!flag && visit[target]<t){
            return 0;
        }
        int m=target;
        while (m!=1){
            m=pre[m];
            ans/=cha[m];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1377().frogPosition(7,new int[][]{{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}},2,4));
    }
}
